{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. 两数相加  \n",
    "给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。  \n",
    "如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。  \n",
    "您可以假设除了数字 0 之外，这两个数都不会以 0 开头。  \n",
    "示例：  \n",
    "输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)  \n",
    "输出：7 -> 0 -> 8  \n",
    "原因：342 + 465 = 807  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def addTwoNumbers(l1, l2):\n",
    "        result = []\n",
    "        carry = 0\n",
    "        while (l1 or l2):\n",
    "            x = l1[0] if l1 else 0\n",
    "            y = l2[0] if l2 else 0\n",
    "            s = x + y + carry\n",
    "            carry = s // 10\n",
    "            result.append(s % 10)\n",
    "            if l1: l1.pop(0)\n",
    "            if l2: l2.pop(0)\n",
    "        if carry > 0:\n",
    "            result.append(1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 1]\n",
      "[7, 1, 4, 4, 5, 6]\n"
     ]
    }
   ],
   "source": [
    "print(Solution.addTwoNumbers([5,4,7], [5,6,4]))\n",
    "print(Solution.addTwoNumbers([2,5,9,8,7], [5,6,4,5,7,5]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. 无重复字符的最长子串  \n",
    "给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。  \n",
    "示例 1:  \n",
    "输入: \"abcabcbb\"  \n",
    "输出: 3   \n",
    "解释: 因为无重复字符的最长子串是 \"abc\"，所以其长度为 3。  \n",
    "示例 2:  \n",
    "输入: \"bbbbb\"  \n",
    "输出: 1  \n",
    "解释: 因为无重复字符的最长子串是 \"b\"，所以其长度为 1。  \n",
    "示例 3:  \n",
    "输入: \"pwwkew\"  \n",
    "输出: 3  \n",
    "解释: 因为无重复字符的最长子串是 \"wke\"，所以其长度为 3。  \n",
    "     请注意，你的答案必须是 子串 的长度，\"pwke\" 是一个子序列，不是子串。  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def lengthOfLongestSubstring(s):\n",
    "        s_length = len(s)\n",
    "        if s_length < 2:\n",
    "            return s_length\n",
    "        # 遍历并记录每次的长度\n",
    "        # result = 0\n",
    "        # for i in range(s_length):\n",
    "        #     j = i + 1\n",
    "        #     d = [s[i]]\n",
    "        #     while j < s_length:\n",
    "        #         if s[j] not in d:\n",
    "        #             d.append(s[j])\n",
    "        #             j += 1\n",
    "        #         else:\n",
    "        #             break\n",
    "        #     if len(d) > result:\n",
    "        #         result = len(d)\n",
    "        # return result\n",
    "        # 滑动窗口\n",
    "        d = set()\n",
    "        p, ans = -1, 0\n",
    "        for i in range(s_length):\n",
    "            if i != 0:\n",
    "                d.remove(s[i - 1])\n",
    "            while p + 1 < s_length and s[p + 1] not in d:\n",
    "                d.add(s[p + 1])\n",
    "                p += 1\n",
    "            ans = max(ans, p - i + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "3\n"
    }
   ],
   "source": [
    "print(Solution.lengthOfLongestSubstring('bvbd'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5. 最长回文子串\n",
    "给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。  \n",
    "示例 1：  \n",
    "输入: \"babad\"  \n",
    "输出: \"bab\"  \n",
    "注意: \"aba\" 也是一个有效答案。  \n",
    "示例 2：  \n",
    "输入: \"cbbd\"  \n",
    "输出: \"bb\"  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def longestPalindrome(s):\n",
    "        # 暴力法，按照长度递减找到解即退出，但是较坏情况下会超时，毕竟有了三重循环\n",
    "        # def condition(s):\n",
    "        #     for i in range(len(s) // 2):\n",
    "        #         if s[i] != s[len(s) - i - 1]:\n",
    "        #             return False\n",
    "        #     return True\n",
    "        # if not s:\n",
    "        #     return s\n",
    "        # s_length = len(s)\n",
    "        # for i in range(1, s_length + 1):\n",
    "        #     for j in range(i):\n",
    "        #         sub_s = s[j: s_length + j - i + 1]\n",
    "        #         if condition(sub_s):\n",
    "        #             return sub_s\n",
    "        # 动态规划，其实官方的这个并不是最优，不过先搬过来了，毕竟下面还有更优解\n",
    "        # n = len(s)\n",
    "        # dp = [[False] * n for _ in range(n)] # 空间存储达到n²，不建议使用此\n",
    "        # ans = ''\n",
    "        # # 枚举子串长度\n",
    "        # for l in range(n):\n",
    "        #     # 枚举子串起始位置，可以得到子串的结束位置\n",
    "        #     for i in range(n):\n",
    "        #         j = i + l # 结束位置\n",
    "        #         if j >= len(s):\n",
    "        #             break\n",
    "        #         if l == 0:\n",
    "        #             dp[i][j] = True\n",
    "        #         elif l == 1:\n",
    "        #             dp[i][j] = (s[i] == s[j])\n",
    "        #         else:\n",
    "        #             dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])\n",
    "        #         if dp[i][j] and l + 1 > len(ans):\n",
    "        #             ans = s[i: j + 1]\n",
    "        # return ans\n",
    "        # 中心扩展\n",
    "        # if not s:\n",
    "        #     return s\n",
    "        # def expandCenter(s, left, right):\n",
    "        #     while left >= 0 and right < len(s) and s[left] == s[right]:\n",
    "        #         left -= 1\n",
    "        #         right += 1\n",
    "        #     return left + 1, right - 1\n",
    "        # start, end = 0, 0\n",
    "        # for i in range(len(s)):\n",
    "        #     # 边界子串视为1或2\n",
    "        #     left1, right1 = expandCenter(s, i, i)\n",
    "        #     left2, right2 = expandCenter(s, i, i + 1)\n",
    "        #     if right1 - left1 > end - start:\n",
    "        #         start, end = left1, right1\n",
    "        #     if right2 - left2 > end - start:\n",
    "        #         start, end = left2, right2\n",
    "        # return s[start: end + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\n"
    }
   ],
   "source": [
    "print(Solution.longestPalindrome(\"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6. Z自行变换\n",
    "将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。  \n",
    "比如输入字符串为 \"LEETCODEISHIRING\" 行数为 3 时，排列如下：  \n",
    "L   C   I   R  \n",
    "E T O E S I I G  \n",
    "E   D   H   N  \n",
    "之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：\"LCIRETOESIIGEDHN\"。  \n",
    "请你实现这个将字符串进行指定行数变换的函数：  \n",
    "string convert(string s, int numRows);  \n",
    "示例 1:  \n",
    "输入: s = \"LEETCODEISHIRING\", numRows = 3  \n",
    "输出: \"LCIRETOESIIGEDHN\"  \n",
    "示例 2:  \n",
    "输入: s = \"LEETCODEISHIRING\", numRows = 4  \n",
    "输出: \"LDREOEIIECIHNTSG\"  \n",
    "解释:  \n",
    "L     D     R  \n",
    "E   O E   I I  \n",
    "E C   I H   N  \n",
    "T     S     G  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def convert(s, numRows):\n",
    "        if numRows == 1: return s\n",
    "        ans = \"\"\n",
    "        # s_length = len(s)\n",
    "        # base = 2 * numRows - 2\n",
    "        # # 按行读取\n",
    "        # for i in range(numRows):\n",
    "        #     # 下一个步长应该是base，并且需要i+j的下标不大于字符串长度\n",
    "        #     for j in range(0, s_length - i, base):\n",
    "        #         ans += s[i + j]\n",
    "        #         # 如果不是首尾两行，需要再增加一个字符\n",
    "        #         if (i != 0 and i != numRows - 1 and j + base - i < s_length):\n",
    "        #             ans += s[j + base - i]\n",
    "        # return ans\n",
    "        # 按行排序\n",
    "        list_s = [\"\" for _ in range(numRows)]\n",
    "        cur_row = 0\n",
    "        down_flag = False\n",
    "        for i in s:\n",
    "            list_s[cur_row] += i\n",
    "            if (cur_row == 0 or cur_row == numRows - 1):\n",
    "                down_flag = not down_flag\n",
    "            cur_row += 1 if down_flag else -1\n",
    "        for row in list_s:\n",
    "            ans += row\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "LCIRETOESIIGEDHN\n"
    }
   ],
   "source": [
    "print(Solution.convert('LEETCODEISHIRING', 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8. 字符串转换整数（atoi）\n",
    "请你来实现一个 atoi 函数，使其能将字符串转换成整数。  \n",
    "首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：  \n",
    "如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。  \n",
    "假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。  \n",
    "该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。  \n",
    "注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。  \n",
    "在任何情况下，若函数不能进行有效的转换时，请返回 0 。  \n",
    "提示：  \n",
    "本题中的空白字符只包括空格字符 ' ' 。  \n",
    "假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。  \n",
    "示例 1:  \n",
    "输入: \"42\"  \n",
    "输出: 42  \n",
    "示例 2:  \n",
    "输入: \"   -42\"  \n",
    "输出: -42  \n",
    "解释: 第一个非空白字符为 '-', 它是一个负号。  \n",
    "     我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。  \n",
    "示例 3:  \n",
    "输入: \"4193 with words\"  \n",
    "输出: 4193  \n",
    "解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。  \n",
    "示例 4:  \n",
    "输入: \"words and 987\"  \n",
    "输出: 0  \n",
    "解释: 第一个非空字符是 'w', 但它不是数字或正、负号。  \n",
    "     因此无法执行有效的转换。  \n",
    "示例 5:  \n",
    "输入: \"-91283472332\"  \n",
    "输出: -2147483648  \n",
    "解释: 数字 \"-91283472332\" 超过 32 位有符号整数范围。   \n",
    "     因此返回 INT_MIN (−231) 。  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def myAtoi(s):\n",
    "        INT_MIN = -2 ** 31\n",
    "        INT_MAX = 2 ** 31 -1\n",
    "        s = s.strip()\n",
    "        if len(s) == 0: return 0\n",
    "        flag = True if s[0] != '-' else False\n",
    "        i = 0\n",
    "        res = 0\n",
    "        if s[0] == '-' or s[0] == '+': i += 1\n",
    "        while (i < len(s) and s[i].isdigit()):\n",
    "            r = ord(s[i]) - ord('0')\n",
    "            if res > INT_MAX // 10 or (res == INT_MAX // 10 and r > 7):\n",
    "                return INT_MAX if flag else INT_MIN\n",
    "            res = res * 10 + r\n",
    "            i += 1\n",
    "        return res if flag else -res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "-2147483648\n"
    }
   ],
   "source": [
    "print(Solution.myAtoi(\"-2147483649\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.盛最多水的容器\n",
    "给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。  \n",
    "说明：你不能倾斜容器，且 n 的值至少为 2。  \n",
    "图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。  \n",
    "示例：  \n",
    "输入：[1,8,6,2,5,4,8,3,7]  \n",
    "输出：49  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def maxArea(height):\n",
    "        l, r = 0, len(height) - 1\n",
    "        ans = 0\n",
    "        while l < r:\n",
    "            area = min(height[l], height[r]) * (r - l)\n",
    "            ans = max(ans, area)\n",
    "            if height[l] <= height[r]:\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "49\n"
    }
   ],
   "source": [
    "print(Solution.maxArea([1,8,6,2,5,4,8,3,7]))"
   ]
  },
  {
   "source": [
    "### 12.整数转罗马数字\n",
    "罗马数字包含以下七种字符： I， V， X， L，C，D 和 M  \n",
    "字符          数值  \n",
    "I             1  \n",
    "V             5  \n",
    "X             10  \n",
    "L             50  \n",
    "C             100  \n",
    "D             500  \n",
    "M             1000  \n",
    "例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。  \n",
    "通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：  \n",
    "I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。  \n",
    "X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。   \n",
    "C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。  \n",
    "给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。  \n",
    "示例 1:  \n",
    "输入: 3  \n",
    "输出: \"III\"  \n",
    "示例 2:  \n",
    "输入: 4  \n",
    "输出: \"IV\"  \n",
    "示例 3:  \n",
    "输入: 9  \n",
    "输出: \"IX\"  \n",
    "示例 4:  \n",
    "输入: 58  \n",
    "输出: \"LVIII\"  \n",
    "解释: L = 50, V = 5, III = 3.  \n",
    "示例 5:  \n",
    "输入: 1994  \n",
    "输出: \"MCMXCIV\"  \n",
    "解释: M = 1000, CM = 900, XC = 90, IV = 4.  "
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def intToRoman(num):\n",
    "        nums = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]\n",
    "        romans = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I']\n",
    "        res = ''\n",
    "        # 从大到小\n",
    "        for i in range(len(nums)):\n",
    "            if num >= nums[i]:\n",
    "                res += (num // nums[i]) * romans[i]\n",
    "                num %= nums[i]\n",
    "        return res"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.8.5 64-bit",
   "language": "python",
   "name": "python38564bitd6b24316ed9c45ef904db727e98f579f"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5-final"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}